/*
 *  Copyright (c) 2011 Mathew Hall.
 *  All rights reserved.
 * 
 *  Redistribution and use in source and binary forms, with or
 *  without modification, are permitted provided that the following conditions
 *  are met:
 * 
 *  Redistributions of source code must retain the above copyright
 *  notice, this list of conditions and the following disclaimer.
 *  Redistributions in binary form must reproduce the above
 *  copyright notice, this list of conditions and the following
 *  disclaimer in the documentation and/or other materials provided
 *  with the distribution.
 *  Neither the name of the University of Sheffield nor the names of its
 *  contributors may be used to endorse or promote products derived
 *  from this software without specific prior written permission.
 * 
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 *  CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 *  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 *  MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 *  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
 *  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 *  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 *  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 *  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 *  OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 *  EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package search.fitnessfunctions;

import primitives.cluster.*;
import primitives.graph.Node;
import static Math.log;
/**
 *
 * @author Mathew Hall
 */
class LutzHMDFF extends TreeFitnessFunction{
    def connected = {it.getTransitionsAsN().size() > 0}
    def unconnected = {it.getTransitionsAsN().size() == 0}
	
    double evaluate(ClusterHead tree) {
        double total = 0;
		
        def modules = [];
         
        
        tree.getChildren().each{if(it.encapsulates()) modules.add(it)}
        
        ClusterNode current; // = modules.first();
        def curr = 0;
        while (curr < modules.size()){
            current = modules.get(curr)
            modules.addAll(current.children.findAll{it.encapsulates()})
            curr++
        }
        
        def cpx=  modules.collect{ 
            module->
            def U_m = unconnectedNodes(module)
            def C_m = connectedNodes(module)
            def M_m = subModules(module)

            def ret;

            ret =  l(U_m.size() + 1)
            ret += l(C_m.size() + 1)
            ret += l(M_m.size() + 1)
            
            def C_mUM_m = []; C_mUM_m.addAll(C_m); C_mUM_m.addAll(M_m);
            
            def F_m = C_mUM_m.collect{
                n->
                f(n)
            }.sum(0)
            
            ret += C_mUM_m.collect{
                n -> 
                def fnOverFm = (double)f(n)/F_m
                l(-log(fnOverFm) - f(n)*log(fnOverFm) )
            }.sum(0)
            
            ret += C_m.collect{
                Node n ->
                def outNodes = n.getTransitionsAsN()
                outNodes.collect{
                    n_ ->
                    l(relDepth(n,lca(n,n_)))
                }.collect{
					if(it <= 0) println "outNodes Sum $it";
					return it;
				}.sum(0)
                
            }.collect{
					if(it<=0) println "C_m sum: $it";
					return it;
			}.sum(0)
            

			if(ret <= 0){
				println "RET $ret";
			}
            return ret
            
            
        }.sum(0)

		return 1/(cpx + Double.MIN_VALUE);
        
        
    }
    

    def static log_2(n){
        return	log((double)n)/log(2)
    }
    
    def static l = {
        n_ ->
		try{
		double n = (double)n_
        log_2(n) + 2 * log_2(log_2(n+1) +1)
	}catch(Exception e){
		e.printStackTrace();
		println("n_: $n_ n:$n")
		return 0
	}
    }
    
    static <T> T randomElement(Collection<T> list){
        def element =(int) (Math.random() * list.size())
        return list.toArray()[element];
    }

    static List<Node> nodesOfFilteredBy(IClusterLevel m, Closure c){
        
        
        IClusterLevel ret;
        //cases:
        // module is a ClusterLeaf (no children) return all its nodes where |trans| > 0
        
        if(!m.encapsulates())
            ret = m
        // OR module is ClusterNode but only has one ClusterLeaf below it, return that child's nodes.
        else if(m.encapsulates() && m.children.findAll{!it.encapsulates()}.size == 1)
            ret =  m.children.findAll{!it.encapsulates()}.getFirst()
        else
            return new LinkedList<Node>()
        
        
        return ret.nodes.findAll{c(it)}
        
        
        
    }
    

    
    
    int f(Node n){
        def trans = n.getTransitionsAsN()
        return trans.size()
    }
    
    int f(IClusterLevel module){
        def nodes = nodesOfFilteredBy(module, {true})
        nodes.collect{ f(it) }.sum(0)
    }
    
    
    List<Node> connectedNodes(IClusterLevel m)  {return  nodesOfFilteredBy(m,connected) }
    List<Node> unconnectedNodes(IClusterLevel m){return  nodesOfFilteredBy(m,unconnected)}
   

    static Collection<IClusterLevel> subModules(IClusterLevel m){
        if(!m.encapsulates() || m.children.size() == 0){
            return new ArrayList<IClusterLevel>();
        }
        return  m.children.findAll{it.encapsulates()}
        
        
    }
    
    static def relDepth(Node a, Node b, IClusterLevel graph){
        
        if(!graph.encapsulates() && graph.nodes.contains(a) && graph.nodes.contains(b)){
            return 0;
        }
        
        def container_a = graph.children.findAll{it.nodes.contains(a)}
        def container_b = graph.children.findAll{it.nodes.contains(b)}
        
        
        def c_a; container_a.each{c_a=it}
        def c_b; container_b.each{c_b=it}
        def ret = 0;
        if(!c_a.equals(c_b)){
            //at current level 2 nodes are in different containers
            
            while(c_b.encapsulates()){
                container_b = c_b.children.findAll{it.nodes.contains(b)}
                assert(container_b.size() ==1)
                container_b.each{c_b=it}
                ret += 1;
            }
            
        }
        return ret;
        
        
    }
    
    static def lca(Node a, Node b, IClusterLevel graph){
        
        if(!graph.encapsulates() && graph.nodes.contains(a) && graph.nodes.contains(b)){
            return graph;
        }
        
        assert(graph.encapsulates())
        def container_a = graph.children.findAll{it.nodes.contains(a)}
        def container_b = graph.children.findAll{it.nodes.contains(b)}
        
        if(container_a.size() == 0 || container_b.size() == 0){
            println "node not found!"
        }
        //The following assertions don't hold.  Why do they not hold?
        //seriously, it doesn't make sense.
        assert(container_a.size() == 1)
        assert(container_b.size() == 1)
        
        def c_a; container_a.each{c_a=it}
        def c_b; container_b.each{c_b=it}
        
        if(!c_a.equals(c_b)) return graph
        
        return lca(a,b,c_a)
        
    }
}

